package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T32 {
    public static void main(String[] args) {
        // )()())
        //
//        System.out.println(new T32().longestValidParentheses(")()())(()()())"));

//        System.out.println(new T32().longestValidParentheses("())"));
        System.out.println(new T32().longestValidParentheses("()(())"));
        System.out.println(new T32().longestValidParentheses2("()(())"));
        System.out.println(new T32().longestValidParentheses3("()(())"));
    }

    public int longestValidParentheses(String s) {
        char[] array = s.toCharArray();
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            int len = process(array, i);
            max = Math.max(len, max);
        }
        return max;
    }

    /***
     *
     * @param array
     * @param i
     * @return
     */
    private int process(char[] array, int i) {
        if (i <= 0) {
            return 0;
        }
        char cur = array[i];
        char pre = array[i - 1];
        if (cur == ')' && pre == '(') {
            return 2 + process(array, i - 2);
        }
        if (cur == '(') {
            return 0;
        }
        int preLen = process(array, i - 1);
        if (preLen == 0) {
            return 0;
        }
        int find = i - preLen - 1;
        //()(())
        if (find >= 0 && array[find] == '(') {
            return process(array, find - 1) + preLen + 2;
        }
        return 0;
    }


    public int longestValidParentheses2(String s) {
        char[] array = s.toCharArray();
        int max = 0;
        int[] cache = new int[array.length];
        Arrays.fill(cache, -1);
        for (int i = 0; i < array.length; i++) {
            int len = process2(array, i, cache);
            max = Math.max(len, max);
        }
        return max;
    }

    /***
     *
     * @param array
     * @param i
     * @return
     */
    private int process2(char[] array, int i, int[] cache) {
        if (i <= 0) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }
        int result = 0;
        char cur = array[i];
        char pre = array[i - 1];
        if (cur == ')' && pre == '(') {
            result = 2 + process2(array, i - 2, cache);
            cache[i] = result;
            return result;
        }
        if (cur == '(') {
            result = 0;
            cache[i] = result;
            return result;
        }
        int preLen = process2(array, i - 1, cache);
        if (preLen == 0) {
            result = 0;
            cache[i] = result;
            return result;
        }
        int find = i - preLen - 1;
        //()(())
        if (find >= 0 && array[find] == '(') {
            result = process2(array, find - 1, cache) + preLen + 2;
            cache[i] = result;
            return result;
        }
        cache[i] = result;
        return result;
    }


    public int longestValidParentheses3(String s) {
        //()(())
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length()];
        int max = 0;

        // dp[i] ==> 以s.charAt(i) 字符结尾，最长回文子串的长度
        for (int i = 1; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur == '(') {
                continue;
            }
            // (((()()()) ) )
            // 01234567891011
            //()))
            char pre = s.charAt(i - 1);
            if (pre == '(') {
                dp[i] = get(dp, i - 2) + 2;
            } else {
                int preLen = get(dp, i - 1);
                if (preLen > 0) {
                    int pairIndex = i - preLen - 1;
                    // ()(())
                    // 012345
                    // 02002
                    if (pairIndex >= 0 && s.charAt(pairIndex) == '(') {
                        dp[i] = preLen + 2 + get(dp, pairIndex - 1);
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    private int get(int[] dp, int i) {
        if (i < 0 || i >= dp.length) {
            return 0;
        }
        return dp[i];
    }
}
